package backtracking;

/**
 * @Author: LDeng
 * @Date: 2021-04-15 8:59
 */
public class Queens {
    public static void main(String[] args) {

        new Queens().placeQueens(4);
    }

    //数组索引是行号， 数组元素是列号 cols[4]=5 第四行 第五列
    int[] cols;
    int ways;//多少种摆法

    void placeQueens(int n) {
        if (n < 1) return;
        cols = new int[n];
        place(0);
        System.out.println(n+" 皇后共有 "+ways+" 种摆法 ");
    }

    //从第row行开始摆放皇后
    void place(int row) {
        if(row==cols.length) {//进到这里表示找到一种方法，
                             // 走到最后一行还能向下一行找就表示成功了
            ways++;
            show();
            return;
        }
        for (int col = 0; col <cols.length; col++) {
            if(isValid(row,col)){
                //在第row行，第col列摆放皇后
                cols[row]=col;
                place(row+1);
                //这步开始回溯
            }
        }
    }

    //判断第row行 第col列是否可以摆放皇后
    boolean isValid(int row,int col){
        for (int i = 0; i < row; i++) {
            //第col列已经有皇后
            if(cols[i]==col){
                System.out.println("["+row+"]["+col+"]=false");
                return false;
            }
            //判断斜线上有没有皇后， 利用斜率
            //(y1-y2)/(x1-x2)=1(-1)
            //if(Math.abs((row-i)/(col-cols[i]))==1) return false;
            if(row-i==Math.abs(col-cols[i])){
                System.out.println("["+row+"]["+col+"]=false");
                return false;
            }
        }
        System.out.println("["+row+"]["+col+"]=true");
        return true;
    }

    void show(){
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if(cols[row]==col){
                    System.out.print("1 ");
                }else{
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("========================");
    }

}





